home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Tcl-Tk 8.0 / Pre-installed version / tcl8.0 / generic / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-15  |  32.3 KB  |  1,334 lines  |  [TEXT/CWIE]
  1. /*
  2.  * TclRegComp and TclRegExec -- TclRegSub is elsewhere
  3.  *
  4.  *    Copyright (c) 1986 by University of Toronto.
  5.  *    Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *    Permission is granted to anyone to use this software for any
  8.  *    purpose on any computer system, and to redistribute it freely,
  9.  *    subject to the following restrictions:
  10.  *
  11.  *    1. The author is not responsible for the consequences of use of
  12.  *        this software, no matter how awful, even if they arise
  13.  *        from defects in it.
  14.  *
  15.  *    2. The origin of this software must not be misrepresented, either
  16.  *        by explicit claim or by omission.
  17.  *
  18.  *    3. Altered versions must be plainly marked as such, and must not
  19.  *        be misrepresented as being the original software.
  20.  *
  21.  * Beware that some of this code is subtly aware of the way operator
  22.  * precedence is structured in regular expressions.  Serious changes in
  23.  * regular-expression syntax might require a total rethink.
  24.  *
  25.  * *** NOTE: this code has been altered slightly for use in Tcl: ***
  26.  * *** 1. Use ckalloc and ckfree instead of  malloc and free.     ***
  27.  * *** 2. Add extra argument to regexp to specify the real     ***
  28.  * ***    start of the string separately from the start of the     ***
  29.  * ***    current search. This is needed to search for multiple     ***
  30.  * ***    matches within a string.                 ***
  31.  * *** 3. Names have been changed, e.g. from regcomp to         ***
  32.  * ***    TclRegComp, to avoid clashes with other          ***
  33.  * ***    regexp implementations used by applications.          ***
  34.  * *** 4. Added errMsg declaration and TclRegError procedure     ***
  35.  * *** 5. Various lint-like things, such as casting arguments     ***
  36.  * ***      in procedure calls.                     ***
  37.  *
  38.  * *** NOTE: This code has been altered for use in MT-Sturdy Tcl ***
  39.  * *** 1. All use of static variables has been changed to access ***
  40.  * ***    fields of a structure.                                 ***
  41.  * *** 2. This in addition to changes to TclRegError makes the   ***
  42.  * ***    code multi-thread safe.                                ***
  43.  *
  44.  * SCCS: @(#) regexp.c 1.13 97/04/29 17:49:17
  45.  */
  46.  
  47. #include "tclInt.h"
  48. #include "tclPort.h"
  49.  
  50. /*
  51.  * The variable below is set to NULL before invoking regexp functions
  52.  * and checked after those functions.  If an error occurred then TclRegError
  53.  * will set the variable to point to a (static) error message.  This
  54.  * mechanism unfortunately does not support multi-threading, but the
  55.  * procedures TclRegError and TclGetRegError can be modified to use
  56.  * thread-specific storage for the variable and thereby make the code
  57.  * thread-safe.
  58.  */
  59.  
  60. static char *errMsg = NULL;
  61.  
  62. /*
  63.  * The "internal use only" fields in regexp.h are present to pass info from
  64.  * compile to execute that permits the execute phase to run lots faster on
  65.  * simple cases.  They are:
  66.  *
  67.  * regstart    char that must begin a match; '\0' if none obvious
  68.  * reganch    is the match anchored (at beginning-of-line only)?
  69.  * regmust    string (pointer into program) that match must include, or NULL
  70.  * regmlen    length of regmust string
  71.  *
  72.  * Regstart and reganch permit very fast decisions on suitable starting points
  73.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  74.  * of lines that cannot possibly match.  The regmust tests are costly enough
  75.  * that TclRegComp() supplies a regmust only if the r.e. contains something
  76.  * potentially expensive (at present, the only such thing detected is * or +
  77.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  78.  * supplied because the test in TclRegExec() needs it and TclRegComp() is
  79.  * computing it anyway.
  80.  */
  81.  
  82. /*
  83.  * Structure for regexp "program".  This is essentially a linear encoding
  84.  * of a nondeterministic finite-state machine (aka syntax charts or
  85.  * "railroad normal form" in parsing technology).  Each node is an opcode
  86.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  87.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  88.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  89.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  90.  * opposed to a collection of them) is never concatenated with anything
  91.  * because of operator precedence.)  The operand of some types of node is
  92.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  93.  * particular, the operand of a BRANCH node is the first node of the branch.
  94.  * (NB this is *not* a tree structure:  the tail of the branch connects
  95.  * to the thing following the set of BRANCHes.)  The opcodes are:
  96.  */
  97.  
  98. /* definition    number    opnd?    meaning */
  99. #define    END    0    /* no    End of program. */
  100. #define    BOL    1    /* no    Match "" at beginning of line. */
  101. #define    EOL    2    /* no    Match "" at end of line. */
  102. #define    ANY    3    /* no    Match any one character. */
  103. #define    ANYOF    4    /* str    Match any character in this string. */
  104. #define    ANYBUT    5    /* str    Match any character not in this string. */
  105. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  106. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  107. #define    EXACTLY    8    /* str    Match this string. */
  108. #define    NOTHING    9    /* no    Match empty string. */
  109. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  110. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  111. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  112.             /*    OPEN+1 is number 1, etc. */
  113. #define    CLOSE    (OPEN+NSUBEXP)    /* no    Analogous to OPEN. */
  114.  
  115. /*
  116.  * Opcode notes:
  117.  *
  118.  * BRANCH    The set of branches constituting a single choice are hooked
  119.  *        together with their "next" pointers, since precedence prevents
  120.  *        anything being concatenated to any individual branch.  The
  121.  *        "next" pointer of the last BRANCH in a choice points to the
  122.  *        thing following the whole choice.  This is also where the
  123.  *        final "next" pointer of each individual branch points; each
  124.  *        branch starts with the operand node of a BRANCH node.
  125.  *
  126.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  127.  *        exists to make loop structures possible.
  128.  *
  129.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  130.  *        BRANCH structures using BACK.  Simple cases (one character
  131.  *        per match) are implemented with STAR and PLUS for speed
  132.  *        and to minimize recursive plunges.
  133.  *
  134.  * OPEN,CLOSE    ...are numbered at compile time.
  135.  */
  136.  
  137. /*
  138.  * A node is one char of opcode followed by two chars of "next" pointer.
  139.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  140.  * value is a positive offset from the opcode of the node containing it.
  141.  * An operand, if any, simply follows the node.  (Note that much of the
  142.  * code generation knows about this implicit relationship.)
  143.  *
  144.  * Using two bytes for the "next" pointer is vast overkill for most things,
  145.  * but allows patterns to get big without disasters.
  146.  */
  147. #define    OP(p)    (*(p))
  148. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  149. #define    OPERAND(p)    ((p) + 3)
  150.  
  151. /*
  152.  * See regmagic.h for one further detail of program structure.
  153.  */
  154.  
  155.  
  156. /*
  157.  * Utility definitions.
  158.  */
  159. #ifndef CHARBITS
  160. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  161. #else
  162. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  163. #endif
  164.  
  165. #define    FAIL(m)    { TclRegError(m); return(NULL); }
  166. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  167. #define    META    "^$.[()|?+*\\"
  168.  
  169. /*
  170.  * Flags to be passed up and down.
  171.  */
  172. #define    HASWIDTH    01    /* Known never to match null string. */
  173. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  174. #define    SPSTART        04    /* Starts with * or +. */
  175. #define    WORST        0    /* Worst case. */
  176.  
  177. /*
  178.  * Global work variables for TclRegComp().
  179.  */
  180. struct regcomp_state  {
  181.     char *regparse;        /* Input-scan pointer. */
  182.     int regnpar;        /* () count. */
  183.     char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  184.     long regsize;        /* Code size. */
  185. };
  186.  
  187. static char regdummy;
  188.  
  189. /*
  190.  * The first byte of the regexp internal "program" is actually this magic
  191.  * number; the start node begins in the second byte.
  192.  */
  193. #define    MAGIC    0234
  194.  
  195.  
  196. /*
  197.  * Forward declarations for TclRegComp()'s friends.
  198.  */
  199.  
  200. static char *        reg _ANSI_ARGS_((int paren, int *flagp,
  201.                 struct regcomp_state *rcstate));
  202. static char *        regatom _ANSI_ARGS_((int *flagp,
  203.                 struct regcomp_state *rcstate));
  204. static char *        regbranch _ANSI_ARGS_((int *flagp,
  205.                 struct regcomp_state *rcstate));
  206. static void        regc _ANSI_ARGS_((int b,
  207.                 struct regcomp_state *rcstate));
  208. static void        reginsert _ANSI_ARGS_((int op, char *opnd,
  209.                 struct regcomp_state *rcstate));
  210. static char *        regnext _ANSI_ARGS_((char *p));
  211. static char *        regnode _ANSI_ARGS_((int op,
  212.                 struct regcomp_state *rcstate));
  213. static void         regoptail _ANSI_ARGS_((char *p, char *val));
  214. static char *        regpiece _ANSI_ARGS_((int *flagp,
  215.                 struct regcomp_state *rcstate));
  216. static void         regtail _ANSI_ARGS_((char *p, char *val));
  217.  
  218. #ifdef STRCSPN
  219. static int strcspn _ANSI_ARGS_((char *s1, char *s2));
  220. #endif
  221.  
  222. /*
  223.  - TclRegComp - compile a regular expression into internal code
  224.  *
  225.  * We can't allocate space until we know how big the compiled form will be,
  226.  * but we can't compile it (and thus know how big it is) until we've got a
  227.  * place to put the code.  So we cheat:  we compile it twice, once with code
  228.  * generation turned off and size counting turned on, and once "for real".
  229.  * This also means that we don't allocate space until we are sure that the
  230.  * thing really will compile successfully, and we never have to move the
  231.  * code and thus invalidate pointers into it.  (Note that it has to be in
  232.  * one piece because free() must be able to free it all.)
  233.  *
  234.  * Beware that the optimization-preparation code in here knows about some
  235.  * of the structure of the compiled regexp.
  236.  */
  237. regexp *
  238. TclRegComp(exp)
  239. char *exp;
  240. {
  241.     register regexp *r;
  242.     register char *scan;
  243.     register char *longest;
  244.     register int len;
  245.     int flags;
  246.     struct regcomp_state state;
  247.     struct regcomp_state *rcstate= &state;
  248.  
  249.     if (exp == NULL)
  250.         FAIL("NULL argument");
  251.  
  252.     /* First pass: determine size, legality. */
  253.     rcstate->regparse = exp;
  254.     rcstate->regnpar = 1;
  255.     rcstate->regsize = 0L;
  256.     rcstate->regcode = ®dummy;
  257.     regc(MAGIC, rcstate);
  258.     if (reg(0, &flags, rcstate) == NULL)
  259.         return(NULL);
  260.  
  261.     /* Small enough for pointer-storage convention? */
  262.     if (rcstate->regsize >= 32767L)        /* Probably could be 65535L. */
  263.         FAIL("regexp too big");
  264.  
  265.     /* Allocate space. */
  266.     r = (regexp *)ckalloc(sizeof(regexp) + (unsigned)rcstate->regsize);
  267.     if (r == NULL)
  268.         FAIL("out of space");
  269.  
  270.     /* Second pass: emit code. */
  271.     rcstate->regparse = exp;
  272.     rcstate->regnpar = 1;
  273.     rcstate->regcode = r->program;
  274.     regc(MAGIC, rcstate);
  275.     if (reg(0, &flags, rcstate) == NULL)
  276.         return(NULL);
  277.  
  278.     /* Dig out information for optimizations. */
  279.     r->regstart = '\0';    /* Worst-case defaults. */
  280.     r->reganch = 0;
  281.     r->regmust = NULL;
  282.     r->regmlen = 0;
  283.     scan = r->program+1;            /* First BRANCH. */
  284.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  285.         scan = OPERAND(scan);
  286.  
  287.         /* Starting-point info. */
  288.         if (OP(scan) == EXACTLY)
  289.             r->regstart = *OPERAND(scan);
  290.         else if (OP(scan) == BOL)
  291.             r->reganch++;
  292.  
  293.         /*
  294.          * If there's something expensive in the r.e., find the
  295.          * longest literal string that must appear and make it the
  296.          * regmust.  Resolve ties in favor of later strings, since
  297.          * the regstart check works with the beginning of the r.e.
  298.          * and avoiding duplication strengthens checking.  Not a
  299.          * strong reason, but sufficient in the absence of others.
  300.          */
  301.         if (flags&SPSTART) {
  302.             longest = NULL;
  303.             len = 0;
  304.             for (; scan != NULL; scan = regnext(scan))
  305.                 if (OP(scan) == EXACTLY && ((int) strlen(OPERAND(scan))) >= len) {
  306.                     longest = OPERAND(scan);
  307.                     len = strlen(OPERAND(scan));
  308.                 }
  309.             r->regmust = longest;
  310.             r->regmlen = len;
  311.         }
  312.     }
  313.  
  314.     return(r);
  315. }
  316.  
  317. /*
  318.  - reg - regular expression, i.e. main body or parenthesized thing
  319.  *
  320.  * Caller must absorb opening parenthesis.
  321.  *
  322.  * Combining parenthesis handling with the base level of regular expression
  323.  * is a trifle forced, but the need to tie the tails of the branches to what
  324.  * follows makes it hard to avoid.
  325.  */
  326. static char *
  327. reg(paren, flagp, rcstate)
  328. int paren;            /* Parenthesized? */
  329. int *flagp;
  330. struct regcomp_state *rcstate;
  331. {
  332.     register char *ret;
  333.     register char *br;
  334.     register char *ender;
  335.     register int parno = 0;
  336.     int flags;
  337.  
  338.     *flagp = HASWIDTH;    /* Tentatively. */
  339.  
  340.     /* Make an OPEN node, if parenthesized. */
  341.     if (paren) {
  342.         if (rcstate->regnpar >= NSUBEXP)
  343.             FAIL("too many ()");
  344.         parno = rcstate->regnpar;
  345.         rcstate->regnpar++;
  346.         ret = regnode(OPEN+parno,rcstate);
  347.     } else
  348.         ret = NULL;
  349.  
  350.     /* Pick up the branches, linking them together. */
  351.     br = regbranch(&flags,rcstate);
  352.     if (br == NULL)
  353.         return(NULL);
  354.     if (ret != NULL)
  355.         regtail(ret, br);    /* OPEN -> first. */
  356.     else
  357.         ret = br;
  358.     if (!(flags&HASWIDTH))
  359.         *flagp &= ~HASWIDTH;
  360.     *flagp |= flags&SPSTART;
  361.     while (*rcstate->regparse == '|') {
  362.         rcstate->regparse++;
  363.         br = regbranch(&flags,rcstate);
  364.         if (br == NULL)
  365.             return(NULL);
  366.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  367.         if (!(flags&HASWIDTH))
  368.             *flagp &= ~HASWIDTH;
  369.         *flagp |= flags&SPSTART;
  370.     }
  371.  
  372.     /* Make a closing node, and hook it on the end. */
  373.     ender = regnode((paren) ? CLOSE+parno : END,rcstate);    
  374.     regtail(ret, ender);
  375.  
  376.     /* Hook the tails of the branches to the closing node. */
  377.     for (br = ret; br != NULL; br = regnext(br))
  378.         regoptail(br, ender);
  379.  
  380.     /* Check for proper termination. */
  381.     if (paren && *rcstate->regparse++ != ')') {
  382.         FAIL("unmatched ()");
  383.     } else if (!paren && *rcstate->regparse != '\0') {
  384.         if (*rcstate->regparse == ')') {
  385.             FAIL("unmatched ()");
  386.         } else
  387.             FAIL("junk on end");    /* "Can't happen". */
  388.         /* NOTREACHED */
  389.     }
  390.  
  391.     return(ret);
  392. }
  393.  
  394. /*
  395.  - regbranch - one alternative of an | operator
  396.  *
  397.  * Implements the concatenation operator.
  398.  */
  399. static char *
  400. regbranch(flagp, rcstate)
  401. int *flagp;
  402. struct regcomp_state *rcstate;
  403. {
  404.     register char *ret;
  405.     register char *chain;
  406.     register char *latest;
  407.     int flags;
  408.  
  409.     *flagp = WORST;        /* Tentatively. */
  410.  
  411.     ret = regnode(BRANCH,rcstate);
  412.     chain = NULL;
  413.     while (*rcstate->regparse != '\0' && *rcstate->regparse != '|' &&
  414.                 *rcstate->regparse != ')') {
  415.         latest = regpiece(&flags, rcstate);
  416.         if (latest == NULL)
  417.             return(NULL);
  418.         *flagp |= flags&HASWIDTH;
  419.         if (chain == NULL)    /* First piece. */
  420.             *flagp |= flags&SPSTART;
  421.         else
  422.             regtail(chain, latest);
  423.         chain = latest;
  424.     }
  425.     if (chain == NULL)    /* Loop ran zero times. */
  426.         (void) regnode(NOTHING,rcstate);
  427.  
  428.     return(ret);
  429. }
  430.  
  431. /*
  432.  - regpiece - something followed by possible [*+?]
  433.  *
  434.  * Note that the branching code sequences used for ? and the general cases
  435.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  436.  * both the endmarker for their branch list and the body of the last branch.
  437.  * It might seem that this node could be dispensed with entirely, but the
  438.  * endmarker role is not redundant.
  439.  */
  440. static char *
  441. regpiece(flagp, rcstate)
  442. int *flagp;
  443. struct regcomp_state *rcstate;
  444. {
  445.     register char *ret;
  446.     register char op;
  447.     register char *next;
  448.     int flags;
  449.  
  450.     ret = regatom(&flags,rcstate);
  451.     if (ret == NULL)
  452.         return(NULL);
  453.  
  454.     op = *rcstate->regparse;
  455.     if (!ISMULT(op)) {
  456.         *flagp = flags;
  457.         return(ret);
  458.     }
  459.  
  460.     if (!(flags&HASWIDTH) && op != '?')
  461.         FAIL("*+ operand could be empty");
  462.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  463.  
  464.     if (op == '*' && (flags&SIMPLE))
  465.         reginsert(STAR, ret, rcstate);
  466.     else if (op == '*') {
  467.         /* Emit x* as (x&|), where & means "self". */
  468.         reginsert(BRANCH, ret, rcstate);            /* Either x */
  469.         regoptail(ret, regnode(BACK,rcstate));        /* and loop */
  470.         regoptail(ret, ret);            /* back */
  471.         regtail(ret, regnode(BRANCH,rcstate));        /* or */
  472.         regtail(ret, regnode(NOTHING,rcstate));        /* null. */
  473.     } else if (op == '+' && (flags&SIMPLE))
  474.         reginsert(PLUS, ret, rcstate);
  475.     else if (op == '+') {
  476.         /* Emit x+ as x(&|), where & means "self". */
  477.         next = regnode(BRANCH,rcstate);            /* Either */
  478.         regtail(ret, next);
  479.         regtail(regnode(BACK,rcstate), ret);        /* loop back */
  480.         regtail(next, regnode(BRANCH,rcstate));        /* or */
  481.         regtail(ret, regnode(NOTHING,rcstate));        /* null. */
  482.     } else if (op == '?') {
  483.         /* Emit x? as (x|) */
  484.         reginsert(BRANCH, ret, rcstate);            /* Either x */
  485.         regtail(ret, regnode(BRANCH,rcstate));        /* or */
  486.         next = regnode(NOTHING,rcstate);        /* null. */
  487.         regtail(ret, next);
  488.         regoptail(ret, next);
  489.     }
  490.     rcstate->regparse++;
  491.     if (ISMULT(*rcstate->regparse))
  492.         FAIL("nested *?+");
  493.  
  494.     return(ret);
  495. }
  496.  
  497. /*
  498.  - regatom - the lowest level
  499.  *
  500.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  501.  * it can turn them into a single node, which is smaller to store and
  502.  * faster to run.  Backslashed characters are exceptions, each becoming a
  503.  * separate node; the code is simpler that way and it's not worth fixing.
  504.  */
  505. static char *
  506. regatom(flagp, rcstate)
  507. int *flagp;
  508. struct regcomp_state *rcstate;
  509. {
  510.     register char *ret;
  511.     int flags;
  512.  
  513.     *flagp = WORST;        /* Tentatively. */
  514.  
  515.     switch (*rcstate->regparse++) {
  516.     case '^':
  517.         ret = regnode(BOL,rcstate);
  518.         break;
  519.     case '$':
  520.         ret = regnode(EOL,rcstate);
  521.         break;
  522.     case '.':
  523.         ret = regnode(ANY,rcstate);
  524.         *flagp |= HASWIDTH|SIMPLE;
  525.         break;
  526.     case '[': {
  527.             register int clss;
  528.             register int classend;
  529.  
  530.             if (*rcstate->regparse == '^') {    /* Complement of range. */
  531.                 ret = regnode(ANYBUT,rcstate);
  532.                 rcstate->regparse++;
  533.             } else
  534.                 ret = regnode(ANYOF,rcstate);
  535.             if (*rcstate->regparse == ']' || *rcstate->regparse == '-')
  536.                 regc(*rcstate->regparse++,rcstate);
  537.             while (*rcstate->regparse != '\0' && *rcstate->regparse != ']') {
  538.                 if (*rcstate->regparse == '-') {
  539.                     rcstate->regparse++;
  540.                     if (*rcstate->regparse == ']' || *rcstate->regparse == '\0')
  541.                         regc('-',rcstate);
  542.                     else {
  543.                         clss = UCHARAT(rcstate->regparse-2)+1;
  544.                         classend = UCHARAT(rcstate->regparse);
  545.                         if (clss > classend+1)
  546.                             FAIL("invalid [] range");
  547.                         for (; clss <= classend; clss++)
  548.                             regc((char)clss,rcstate);
  549.                         rcstate->regparse++;
  550.                     }
  551.                 } else
  552.                     regc(*rcstate->regparse++,rcstate);
  553.             }
  554.             regc('\0',rcstate);
  555.             if (*rcstate->regparse != ']')
  556.                 FAIL("unmatched []");
  557.             rcstate->regparse++;
  558.             *flagp |= HASWIDTH|SIMPLE;
  559.         }
  560.         break;
  561.     case '(':
  562.         ret = reg(1, &flags, rcstate);
  563.         if (ret == NULL)
  564.             return(NULL);
  565.         *flagp |= flags&(HASWIDTH|SPSTART);
  566.         break;
  567.     case '\0':
  568.     case '|':
  569.     case ')':
  570.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  571.         /* NOTREACHED */
  572.     case '?':
  573.     case '+':
  574.     case '*':
  575.         FAIL("?+* follows nothing");
  576.         /* NOTREACHED */
  577.     case '\\':
  578.         if (*rcstate->regparse == '\0')
  579.             FAIL("trailing \\");
  580.         ret = regnode(EXACTLY,rcstate);
  581.         regc(*rcstate->regparse++,rcstate);
  582.         regc('\0',rcstate);
  583.         *flagp |= HASWIDTH|SIMPLE;
  584.         break;
  585.     default: {
  586.             register int len;
  587.             register char ender;
  588.  
  589.             rcstate->regparse--;
  590.             len = strcspn(rcstate->regparse, META);
  591.             if (len <= 0)
  592.                 FAIL("internal disaster");
  593.             ender = *(rcstate->regparse+len);
  594.             if (len > 1 && ISMULT(ender))
  595.                 len--;        /* Back off clear of ?+* operand. */
  596.             *flagp |= HASWIDTH;
  597.             if (len == 1)
  598.                 *flagp |= SIMPLE;
  599.             ret = regnode(EXACTLY,rcstate);
  600.             while (len > 0) {
  601.                 regc(*rcstate->regparse++,rcstate);
  602.                 len--;
  603.             }
  604.             regc('\0',rcstate);
  605.         }
  606.         break;
  607.     }
  608.  
  609.     return(ret);
  610. }
  611.  
  612. /*
  613.  - regnode - emit a node
  614.  */
  615. static char *            /* Location. */
  616. regnode(op, rcstate)
  617. int op;
  618. struct regcomp_state *rcstate;
  619. {
  620.     register char *ret;
  621.     register char *ptr;
  622.  
  623.     ret = rcstate->regcode;
  624.     if (ret == ®dummy) {
  625.         rcstate->regsize += 3;
  626.         return(ret);
  627.     }
  628.  
  629.     ptr = ret;
  630.     *ptr++ = (char)op;
  631.     *ptr++ = '\0';        /* Null "next" pointer. */
  632.     *ptr++ = '\0';
  633.     rcstate->regcode = ptr;
  634.  
  635.     return(ret);
  636. }
  637.  
  638. /*
  639.  - regc - emit (if appropriate) a byte of code
  640.  */
  641. static void
  642. regc(b, rcstate)
  643. int b;
  644. struct regcomp_state *rcstate;
  645. {
  646.     if (rcstate->regcode != ®dummy)
  647.         *rcstate->regcode++ = (char)b;
  648.     else
  649.         rcstate->regsize++;
  650. }
  651.  
  652. /*
  653.  - reginsert - insert an operator in front of already-emitted operand
  654.  *
  655.  * Means relocating the operand.
  656.  */
  657. static void
  658. reginsert(op, opnd, rcstate)
  659. int op;
  660. char *opnd;
  661. struct regcomp_state *rcstate;
  662. {
  663.     register char *src;
  664.     register char *dst;
  665.     register char *place;
  666.  
  667.     if (rcstate->regcode == ®dummy) {
  668.         rcstate->regsize += 3;
  669.         return;
  670.     }
  671.  
  672.     src = rcstate->regcode;
  673.     rcstate->regcode += 3;
  674.     dst = rcstate->regcode;
  675.     while (src > opnd)
  676.         *--dst = *--src;
  677.  
  678.     place = opnd;        /* Op node, where operand used to be. */
  679.     *place++ = (char)op;
  680.     *place++ = '\0';
  681.     *place = '\0';
  682. }
  683.  
  684. /*
  685.  - regtail - set the next-pointer at the end of a node chain
  686.  */
  687. static void
  688. regtail(p, val)
  689. char *p;
  690. char *val;
  691. {
  692.     register char *scan;
  693.     register char *temp;
  694.     register int offset;
  695.  
  696.     if (p == ®dummy)
  697.         return;
  698.  
  699.     /* Find last node. */
  700.     scan = p;
  701.     for (;;) {
  702.         temp = regnext(scan);
  703.         if (temp == NULL)
  704.             break;
  705.         scan = temp;
  706.     }
  707.  
  708.     if (OP(scan) == BACK)
  709.         offset = scan - val;
  710.     else
  711.         offset = val - scan;
  712.     *(scan+1) = (char)((offset>>8)&0377);
  713.     *(scan+2) = (char)(offset&0377);
  714. }
  715.  
  716. /*
  717.  - regoptail - regtail on operand of first argument; nop if operandless
  718.  */
  719. static void
  720. regoptail(p, val)
  721. char *p;
  722. char *val;
  723. {
  724.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  725.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  726.         return;
  727.     regtail(OPERAND(p), val);
  728. }
  729.  
  730. /*
  731.  * TclRegExec and friends
  732.  */
  733.  
  734. /*
  735.  * Global work variables for TclRegExec().
  736.  */
  737. struct regexec_state  {
  738.     char *reginput;        /* String-input pointer. */
  739.     char *regbol;        /* Beginning of input, for ^ check. */
  740.     char **regstartp;    /* Pointer to startp array. */
  741.     char **regendp;        /* Ditto for endp. */
  742. };
  743.  
  744. /*
  745.  * Forwards.
  746.  */
  747. static int         regtry _ANSI_ARGS_((regexp *prog, char *string,
  748.                 struct regexec_state *restate));
  749. static int         regmatch _ANSI_ARGS_((char *prog,
  750.                 struct regexec_state *restate));
  751. static int         regrepeat _ANSI_ARGS_((char *p,
  752.                 struct regexec_state *restate));
  753.  
  754. #ifdef DEBUG
  755. int regnarrate = 0;
  756. void regdump _ANSI_ARGS_((regexp *r));
  757. static char *regprop _ANSI_ARGS_((char *op));
  758. #endif
  759.  
  760. /*
  761.  - TclRegExec - match a regexp against a string
  762.  */
  763. int
  764. TclRegExec(prog, string, start)
  765. register regexp *prog;
  766. register char *string;
  767. char *start;
  768. {
  769.     register char *s;
  770.     struct regexec_state state;
  771.     struct regexec_state *restate= &state;
  772.  
  773.     /* Be paranoid... */
  774.     if (prog == NULL || string == NULL) {
  775.         TclRegError("NULL parameter");
  776.         return(0);
  777.     }
  778.  
  779.     /* Check validity of program. */
  780.     if (UCHARAT(prog->program) != MAGIC) {
  781.         TclRegError("corrupted program");
  782.         return(0);
  783.     }
  784.  
  785.     /* If there is a "must appear" string, look for it. */
  786.     if (prog->regmust != NULL) {
  787.         s = string;
  788.         while ((s = strchr(s, prog->regmust[0])) != NULL) {
  789.             if (strncmp(s, prog->regmust, (size_t) prog->regmlen)
  790.                 == 0)
  791.                 break;    /* Found it. */
  792.             s++;
  793.         }
  794.         if (s == NULL)    /* Not present. */
  795.             return(0);
  796.     }
  797.  
  798.     /* Mark beginning of line for ^ . */
  799.     restate->regbol = start;
  800.  
  801.     /* Simplest case:  anchored match need be tried only once. */
  802.     if (prog->reganch)
  803.         return(regtry(prog, string, restate));
  804.  
  805.     /* Messy cases:  unanchored match. */
  806.     s = string;
  807.     if (prog->regstart != '\0')
  808.         /* We know what char it must start with. */
  809.         while ((s = strchr(s, prog->regstart)) != NULL) {
  810.             if (regtry(prog, s, restate))
  811.                 return(1);
  812.             s++;
  813.         }
  814.     else
  815.         /* We don't -- general case. */
  816.         do {
  817.             if (regtry(prog, s, restate))
  818.                 return(1);
  819.         } while (*s++ != '\0');
  820.  
  821.     /* Failure. */
  822.     return(0);
  823. }
  824.  
  825. /*
  826.  - regtry - try match at specific point
  827.  */
  828. static int            /* 0 failure, 1 success */
  829. regtry(prog, string, restate)
  830. regexp *prog;
  831. char *string;
  832. struct regexec_state *restate;
  833. {
  834.     register int i;
  835.     register char **sp;
  836.     register char **ep;
  837.  
  838.     restate->reginput = string;
  839.     restate->regstartp = prog->startp;
  840.     restate->regendp = prog->endp;
  841.  
  842.     sp = prog->startp;
  843.     ep = prog->endp;
  844.     for (i = NSUBEXP; i > 0; i--) {
  845.         *sp++ = NULL;
  846.         *ep++ = NULL;
  847.     }
  848.     if (regmatch(prog->program + 1,restate)) {
  849.         prog->startp[0] = string;
  850.         prog->endp[0] = restate->reginput;
  851.         return(1);
  852.     } else
  853.         return(0);
  854. }
  855.  
  856. /*
  857.  - regmatch - main matching routine
  858.  *
  859.  * Conceptually the strategy is simple:  check to see whether the current
  860.  * node matches, call self recursively to see whether the rest matches,
  861.  * and then act accordingly.  In practice we make some effort to avoid
  862.  * recursion, in particular by going through "ordinary" nodes (that don't
  863.  * need to know whether the rest of the match failed) by a loop instead of
  864.  * by recursion.
  865.  */
  866. static int            /* 0 failure, 1 success */
  867. regmatch(prog, restate)
  868. char *prog;
  869. struct regexec_state *restate;
  870. {
  871.     register char *scan;    /* Current node. */
  872.     char *next;        /* Next node. */
  873.  
  874.     scan = prog;
  875. #ifdef DEBUG
  876.     if (scan != NULL && regnarrate)
  877.     fprintf(stderr, "%s(\n", regprop(scan));
  878. #endif
  879.     while (scan != NULL) {
  880. #ifdef DEBUG
  881.     if (regnarrate)
  882.         fprintf(stderr, "%s...\n", regprop(scan));
  883. #endif
  884.     next = regnext(scan);
  885.  
  886.     switch (OP(scan)) {
  887.         case BOL:
  888.         if (restate->reginput != restate->regbol) {
  889.             return 0;
  890.         }
  891.         break;
  892.         case EOL:
  893.         if (*restate->reginput != '\0') {
  894.             return 0;
  895.         }
  896.         break;
  897.         case ANY:
  898.         if (*restate->reginput == '\0') {
  899.             return 0;
  900.         }
  901.         restate->reginput++;
  902.         break;
  903.         case EXACTLY: {
  904.         register int len;
  905.         register char *opnd;
  906.  
  907.         opnd = OPERAND(scan);
  908.         /* Inline the first character, for speed. */
  909.         if (*opnd != *restate->reginput) {
  910.             return 0 ;
  911.         }
  912.         len = strlen(opnd);
  913.         if (len > 1 && strncmp(opnd, restate->reginput, (size_t) len)
  914.             != 0) {
  915.             return 0;
  916.         }
  917.         restate->reginput += len;
  918.         break;
  919.         }
  920.         case ANYOF:
  921.         if (*restate->reginput == '\0'
  922.             || strchr(OPERAND(scan), *restate->reginput) == NULL) {
  923.             return 0;
  924.         }
  925.         restate->reginput++;
  926.         break;
  927.         case ANYBUT:
  928.         if (*restate->reginput == '\0'
  929.             || strchr(OPERAND(scan), *restate->reginput) != NULL) {
  930.             return 0;
  931.         }
  932.         restate->reginput++;
  933.         break;
  934.         case NOTHING:
  935.         break;
  936.         case BACK:
  937.         break;
  938.         case OPEN+1:
  939.         case OPEN+2:
  940.         case OPEN+3:
  941.         case OPEN+4:
  942.         case OPEN+5:
  943.         case OPEN+6:
  944.         case OPEN+7:
  945.         case OPEN+8:
  946.         case OPEN+9: {
  947.         register int no;
  948.         register char *save;
  949.  
  950.     doOpen:
  951.         no = OP(scan) - OPEN;
  952.         save = restate->reginput;
  953.  
  954.         if (regmatch(next,restate)) {
  955.             /*
  956.              * Don't set startp if some later invocation of the
  957.              * same parentheses already has.
  958.              */
  959.             if (restate->regstartp[no] == NULL) {
  960.             restate->regstartp[no] = save;
  961.             }
  962.             return 1;
  963.         } else {
  964.             return 0;
  965.         }
  966.         }
  967.         case CLOSE+1:
  968.         case CLOSE+2:
  969.         case CLOSE+3:
  970.         case CLOSE+4:
  971.         case CLOSE+5:
  972.         case CLOSE+6:
  973.         case CLOSE+7:
  974.         case CLOSE+8:
  975.         case CLOSE+9: {
  976.         register int no;
  977.         register char *save;
  978.  
  979.     doClose:
  980.         no = OP(scan) - CLOSE;
  981.         save = restate->reginput;
  982.  
  983.         if (regmatch(next,restate)) {
  984.                 /*
  985.                  * Don't set endp if some later
  986.                  * invocation of the same parentheses
  987.                  * already has.
  988.                  */
  989.             if (restate->regendp[no] == NULL)
  990.             restate->regendp[no] = save;
  991.             return 1;
  992.         } else {
  993.             return 0;
  994.         }
  995.         }
  996.         case BRANCH: {
  997.         register char *save;
  998.  
  999.         if (OP(next) != BRANCH) { /* No choice. */
  1000.             next = OPERAND(scan); /* Avoid recursion. */
  1001.         } else {
  1002.             do {
  1003.             save = restate->reginput;
  1004.             if (regmatch(OPERAND(scan),restate))
  1005.                 return(1);
  1006.             restate->reginput = save;
  1007.             scan = regnext(scan);
  1008.             } while (scan != NULL && OP(scan) == BRANCH);
  1009.             return 0;
  1010.         }
  1011.         break;
  1012.         }
  1013.         case STAR:
  1014.         case PLUS: {
  1015.         register char nextch;
  1016.         register int no;
  1017.         register char *save;
  1018.         register int min;
  1019.  
  1020.         /*
  1021.          * Lookahead to avoid useless match attempts
  1022.          * when we know what character comes next.
  1023.          */
  1024.         nextch = '\0';
  1025.         if (OP(next) == EXACTLY)
  1026.             nextch = *OPERAND(next);
  1027.         min = (OP(scan) == STAR) ? 0 : 1;
  1028.         save = restate->reginput;
  1029.         no = regrepeat(OPERAND(scan),restate);
  1030.         while (no >= min) {
  1031.             /* If it could work, try it. */
  1032.             if (nextch == '\0' || *restate->reginput == nextch)
  1033.             if (regmatch(next,restate))
  1034.                 return(1);
  1035.             /* Couldn't or didn't -- back up. */
  1036.             no--;
  1037.             restate->reginput = save + no;
  1038.         }
  1039.         return(0);
  1040.         }
  1041.         case END:
  1042.         return(1);    /* Success! */
  1043.         default:
  1044.         if (OP(scan) > OPEN && OP(scan) < OPEN+NSUBEXP) {
  1045.             goto doOpen;
  1046.         } else if (OP(scan) > CLOSE && OP(scan) < CLOSE+NSUBEXP) {
  1047.             goto doClose;
  1048.         }
  1049.         TclRegError("memory corruption");
  1050.         return 0;
  1051.     }
  1052.  
  1053.     scan = next;
  1054.     }
  1055.  
  1056.     /*
  1057.      * We get here only if there's trouble -- normally "case END" is
  1058.      * the terminating point.
  1059.      */
  1060.     TclRegError("corrupted pointers");
  1061.     return(0);
  1062. }
  1063.  
  1064. /*
  1065.  - regrepeat - repeatedly match something simple, report how many
  1066.  */
  1067. static int
  1068. regrepeat(p, restate)
  1069. char *p;
  1070. struct regexec_state *restate;
  1071. {
  1072.     register int count = 0;
  1073.     register char *scan;
  1074.     register char *opnd;
  1075.  
  1076.     scan = restate->reginput;
  1077.     opnd = OPERAND(p);
  1078.     switch (OP(p)) {
  1079.     case ANY:
  1080.         count = strlen(scan);
  1081.         scan += count;
  1082.         break;
  1083.     case EXACTLY:
  1084.         while (*opnd == *scan) {
  1085.             count++;
  1086.             scan++;
  1087.         }
  1088.         break;
  1089.     case ANYOF:
  1090.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1091.             count++;
  1092.             scan++;
  1093.         }
  1094.         break;
  1095.     case ANYBUT:
  1096.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1097.             count++;
  1098.             scan++;
  1099.         }
  1100.         break;
  1101.     default:        /* Oh dear.  Called inappropriately. */
  1102.         TclRegError("internal foulup");
  1103.         count = 0;    /* Best compromise. */
  1104.         break;
  1105.     }
  1106.     restate->reginput = scan;
  1107.  
  1108.     return(count);
  1109. }
  1110.  
  1111. /*
  1112.  - regnext - dig the "next" pointer out of a node
  1113.  */
  1114. static char *
  1115. regnext(p)
  1116. register char *p;
  1117. {
  1118.     register int offset;
  1119.  
  1120.     if (p == ®dummy)
  1121.         return(NULL);
  1122.  
  1123.     offset = NEXT(p);
  1124.     if (offset == 0)
  1125.         return(NULL);
  1126.  
  1127.     if (OP(p) == BACK)
  1128.         return(p-offset);
  1129.     else
  1130.         return(p+offset);
  1131. }
  1132.  
  1133. #ifdef DEBUG
  1134.  
  1135. static char *regprop();
  1136.  
  1137. /*
  1138.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1139.  */
  1140. void
  1141. regdump(r)
  1142. regexp *r;
  1143. {
  1144.     register char *s;
  1145.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1146.     register char *next;
  1147.  
  1148.  
  1149.     s = r->program + 1;
  1150.     while (op != END) {    /* While that wasn't END last time... */
  1151.         op = OP(s);
  1152.         printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1153.         next = regnext(s);
  1154.         if (next == NULL)        /* Next ptr. */
  1155.             printf("(0)");
  1156.         else 
  1157.             printf("(%d)", (s-r->program)+(next-s));
  1158.         s += 3;
  1159.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1160.             /* Literal string, where present. */
  1161.             while (*s != '\0') {
  1162.                 putchar(*s);
  1163.                 s++;
  1164.             }
  1165.             s++;
  1166.         }
  1167.         putchar('\n');
  1168.     }
  1169.  
  1170.     /* Header fields of interest. */
  1171.     if (r->regstart != '\0')
  1172.         printf("start `%c' ", r->regstart);
  1173.     if (r->reganch)
  1174.         printf("anchored ");
  1175.     if (r->regmust != NULL)
  1176.         printf("must have \"%s\"", r->regmust);
  1177.     printf("\n");
  1178. }
  1179.  
  1180. /*
  1181.  - regprop - printable representation of opcode
  1182.  */
  1183. static char *
  1184. regprop(op)
  1185. char *op;
  1186. {
  1187.     register char *p;
  1188.     static char buf[50];
  1189.  
  1190.     (void) strcpy(buf, ":");
  1191.  
  1192.     switch (OP(op)) {
  1193.     case BOL:
  1194.         p = "BOL";
  1195.         break;
  1196.     case EOL:
  1197.         p = "EOL";
  1198.         break;
  1199.     case ANY:
  1200.         p = "ANY";
  1201.         break;
  1202.     case ANYOF:
  1203.         p = "ANYOF";
  1204.         break;
  1205.     case ANYBUT:
  1206.         p = "ANYBUT";
  1207.         break;
  1208.     case BRANCH:
  1209.         p = "BRANCH";
  1210.         break;
  1211.     case EXACTLY:
  1212.         p = "EXACTLY";
  1213.         break;
  1214.     case NOTHING:
  1215.         p = "NOTHING";
  1216.         break;
  1217.     case BACK:
  1218.         p = "BACK";
  1219.         break;
  1220.     case END:
  1221.         p = "END";
  1222.         break;
  1223.     case OPEN+1:
  1224.     case OPEN+2:
  1225.     case OPEN+3:
  1226.     case OPEN+4:
  1227.     case OPEN+5:
  1228.     case OPEN+6:
  1229.     case OPEN+7:
  1230.     case OPEN+8:
  1231.     case OPEN+9:
  1232.         sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1233.         p = NULL;
  1234.         break;
  1235.     case CLOSE+1:
  1236.     case CLOSE+2:
  1237.     case CLOSE+3:
  1238.     case CLOSE+4:
  1239.     case CLOSE+5:
  1240.     case CLOSE+6:
  1241.     case CLOSE+7:
  1242.     case CLOSE+8:
  1243.     case CLOSE+9:
  1244.         sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1245.         p = NULL;
  1246.         break;
  1247.     case STAR:
  1248.         p = "STAR";
  1249.         break;
  1250.     case PLUS:
  1251.         p = "PLUS";
  1252.         break;
  1253.     default:
  1254.         if (OP(op) > OPEN && OP(op) < OPEN+NSUBEXP) {
  1255.             sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1256.             p = NULL;
  1257.             break;
  1258.         } else if (OP(op) > CLOSE && OP(op) < CLOSE+NSUBEXP) {
  1259.             sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1260.             p = NULL;
  1261.         } else {
  1262.             TclRegError("corrupted opcode");
  1263.         }
  1264.         break;
  1265.     }
  1266.     if (p != NULL)
  1267.         (void) strcat(buf, p);
  1268.     return(buf);
  1269. }
  1270. #endif
  1271.  
  1272. /*
  1273.  * The following is provided for those people who do not have strcspn() in
  1274.  * their C libraries.  They should get off their butts and do something
  1275.  * about it; at least one public-domain implementation of those (highly
  1276.  * useful) string routines has been published on Usenet.
  1277.  */
  1278. #ifdef STRCSPN
  1279. /*
  1280.  * strcspn - find length of initial segment of s1 consisting entirely
  1281.  * of characters not from s2
  1282.  */
  1283.  
  1284. static int
  1285. strcspn(s1, s2)
  1286. char *s1;
  1287. char *s2;
  1288. {
  1289.     register char *scan1;
  1290.     register char *scan2;
  1291.     register int count;
  1292.  
  1293.     count = 0;
  1294.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1295.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1296.             if (*scan1 == *scan2++)
  1297.                 return(count);
  1298.         count++;
  1299.     }
  1300.     return(count);
  1301. }
  1302. #endif
  1303.  
  1304. /*
  1305.  *----------------------------------------------------------------------
  1306.  *
  1307.  * TclRegError --
  1308.  *
  1309.  *    This procedure is invoked by the regexp code when an error
  1310.  *    occurs.  It saves the error message so it can be seen by the
  1311.  *    code that called Spencer's code.
  1312.  *
  1313.  * Results:
  1314.  *    None.
  1315.  *
  1316.  * Side effects:
  1317.  *    The value of "string" is saved in "errMsg".
  1318.  *
  1319.  *----------------------------------------------------------------------
  1320.  */
  1321.  
  1322. void
  1323. TclRegError(string)
  1324.     char *string;            /* Error message. */
  1325. {
  1326.     errMsg = string;
  1327. }
  1328.  
  1329. char *
  1330. TclGetRegError()
  1331. {
  1332.     return errMsg;
  1333. }
  1334.